package com.example;

public class HouseRobberIii {
    
    class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    public int rob(TreeNode root) {
        int[] helper = helper(root);
        return Math.max(helper[0], helper[1]);
    }

    private int[] helper(TreeNode treeNode){
        int[] res = new int[2];
        if(treeNode == null){
            return res;
        }
        // 后序遍历
        int[] left = helper(treeNode.left);
        int[] right = helper(treeNode.right);
        // 下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
        // 不偷：Max(左孩子不偷，左孩子偷) + Max(又孩子不偷，右孩子偷)
        res[0]= Math.max(left[0], left[1])+ Math.max(right[0], right[1]);
        // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
        res[1] = treeNode.val + left[0] + right[0];
        return res;
    }
}
